# # -*- coding: utf-8 -*-
# # Python中默认的编码格式是 ASCII 格式，在没修改编码格式时无法正确打印汉字，所以在读取中文时会报错。

# 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，
# 返回一个长度为 n + 1 的数组 ans 作为答案。

# 输入：n = 2
# 输出：[0,1,1]
# 解释：
# 0 --> 0
# 1 --> 1
# 2 --> 10

# 输入：n = 5
# 输出：[0,1,1,2,1,2]
# 解释：
# 0 --> 0
# 1 --> 1
# 2 --> 10
# 3 --> 11
# 4 --> 100
# 5 --> 101

def countBits(num):
    """
    1: 0001     3:  0011      0: 0000
    2: 0010     6:  0110      1: 0001
    4: 0100     12: 1100      2: 0010
    8: 1000     24: 11000     3: 0011
    16:10000    48: 110000    4: 0100
    32:100000   96: 1100000   5: 0101

    由上可见：
    1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。
    2、如果 i 为奇数，那么f(i) = f(i - 1) + 1， 因为如果i为奇数，那么 i - 1必定为偶数，而偶数的二进制最低位一定是0，
    那么该偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i - 1) + 1。
    :type num: int
    :rtype: List[int]
    """
    ret = [0]
    for i in range(1,num+1):
        if i % 2 == 0:  # 偶数
            ret.append(ret[i // 2])
        else:  # 奇数
            ret.append(ret[i - 1] + 1)
    return ret

print(countBits(5))